import random

import numpy as np

from collections import deque

# from my_videos.games.eight_puzzle_game.fifteen_puzzle import LEN
LEN = 5
ANSWER = np.roll(np.arange(LEN ** 2), -1)
DIR = [-1, -LEN, LEN, 1]
DX = [0, -1, 1, 0]
DY = [-1, 0, 0, 1]


class MapState:
    def __init__(self,
                 data: np.ndarray = np.zeros(LEN ** 2),
                 parent: int = 0,
                 operation: int = 0,
                 step: int = 0,
                 value: int = 0):
        self.parent = parent
        self.operation = operation
        self.step = step
        self.value = value
        self.data = np.array(data, dtype=np.int32)

    def swap_value(self, u, v):
        self.data[u], self.data[v] = self.data[v], self.data[u]

    def set_value(self, value):
        self.value = value

    def __eq__(self, other):
        return (other.data == self.data).all()


def _evaluate_distance(state: MapState):
    query = np.where(state.data != ANSWER)[0]
    return len(query)


def _get_array_that_ai_larger_than_previous_numbers(array: np.ndarray) -> np.ndarray:
    res = np.zeros(LEN ** 2 - 1)
    mask = array != 0
    sub_arr = array[mask]
    for i in range(1, len(sub_arr)):
        query = np.where(sub_arr[:i] < sub_arr[i])[0]
        res[i] = len(query)
    return res


def has_answer(start: np.ndarray) -> bool:
    sum_array = sum(_get_array_that_ai_larger_than_previous_numbers(start))
    return sum_array % 2 == 0


def _insert_in_order(q: deque, t: MapState):
    index = 0
    for i in range(q.__len__()):
        if q[i].value >= t.value:
            index = i
            break
    q.insert(index, t)


def _extend_node(qclosed: deque, qopen: deque, tmp: MapState, parent: int):
    zero_index = np.where(tmp.data == 0)[0][0]
    row, col = zero_index // LEN, zero_index % 4
    for i in range(4):
        nrow, ncol = row + DX[i], col + DY[i]
        if 0 <= nrow < 4 and 0 <= ncol < 4:
            zero_new = nrow * 4 + ncol
            new_node = MapState(tmp.data, parent, tmp.data[zero_new], tmp.step + 1, 0)
            new_node.swap_value(zero_new, zero_index)
            new_node.set_value(_evaluate_distance(new_node))

            try:
                in_open_index = qopen.index(new_node)
            except ValueError:
                in_open_index = -1
            try:
                in_closed_index = qclosed.index(new_node)
            except ValueError:
                in_closed_index = -1

            if in_open_index == -1 and in_closed_index == -1:
                _insert_in_order(qopen, new_node)
            elif in_open_index != -1:
                if new_node.value < qopen[in_open_index].value:
                    qopen[in_open_index].parent = new_node.parent
                    qopen[in_open_index].value = new_node.value
            elif in_closed_index != -1:
                if new_node.value < qclosed[in_closed_index].value:
                    _insert_in_order(qopen, new_node)


def _get_answer(qclosed: deque):
    operation_list = []
    parent = qclosed.__len__()
    while parent != 0:
        operation_list.insert(0, qclosed[parent - 1].operation)
        parent = qclosed[parent - 1].parent
    return operation_list


def puzzle_solution(start):
    assert (len(start) == LEN ** 2)
    qopen = deque()
    qclosed = deque()
    start_node = MapState(start, 0, 0, 0, _evaluate_distance(start))
    qopen.append(start_node)
    while qopen:
        tmp = qopen.popleft()
        qclosed.append(tmp)
        if _evaluate_distance(tmp.data) == 0:
            return _get_answer(qclosed)
        parent = qclosed.__len__()
        _extend_node(qclosed, qopen, tmp, parent)


if __name__ == "__main__":
    # src = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11, 13, 14, 15, 12])
    src = np.array([13, 2, 4, 8, 15, 1, 10, 9, 7, 14, 5, 12, 0, 6, 11, 3])
    result = puzzle_solution(src)
    print(result)
